package backtrack;
import java.util.*;
public class _07_93_复原IP地址 {
	List<List<Integer>> result = new ArrayList<>();
	List<Integer> item = new ArrayList<>();
	List<String> strResult = new ArrayList<>();
	StringBuilder stb;
    public List<String> restoreIpAddresses(String s) {

    	backtracking(s,0);
    	
    	for (List<Integer> i : result) {
    		stb = new StringBuilder();
    		for (Integer j : i)  {
				stb.append(j + ".");
			}
			stb.deleteCharAt(stb.length() - 1);
			strResult.add(stb.toString());
		}
    	
    	return strResult;
    }
    
    public void backtracking(String s, int index) {
    	// 控制item内只能有4个值，且已经把所有的数字遍历完成
    	if(item.size() == 4 && index == s.length()) {
//    		System.out.println(item);
    		result.add(new ArrayList<Integer>(item));
    		return;
    	}
    	
    	for(int i = index; i < s.length(); i++) {
    		String str = s.substring(index, i + 1);
    		// 长度大于1，判断前导是否为0，为0则不合法，跳过这一层
    		if(str.length() > 1 && str.charAt(0) == '0') {
    			break;
    		}
    		// 长度大于三，则跳出这一层
    		if(str.length() > 3) {
    			break;
    		}
    		// 解析成数字，然后判断是否在ip范围内，不是则跳出这一层
    		// 在合法范围内则新增ip
    		int ip = Integer.parseInt(str);
    		if(ip >= 0 && ip <= 255) {
    			item.add(ip);
    		} else {
    			break;
    		}
    		backtracking(s, i + 1);
    		item.remove(item.size() - 1);
    	}
    }
    public static void main(String[] args) {
		new _07_93_复原IP地址().restoreIpAddresses("1111111111111111111");
	}
}
